import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-06-25
 * Time: 23:33
 */
//https://leetcode.cn/problems/implement-stack-using-queues/submissions/639219334/
    //请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
class MyStack {
    LinkedList<Integer> q1;
    LinkedList<Integer> q2;

    public MyStack() {
        q1=new LinkedList();
        q2=new LinkedList();
    }

    public void push(int x) {
        if(q1.isEmpty()){
            q2.offer(x);
        }
        else {
            q1.offer(x);
        }
    }

    public int pop() {
        int n=0;
        if(q1.isEmpty()){
            while(!q2.isEmpty()){
                n=q2.poll();
                if(q2.isEmpty()){
                    return n;
                }
                q1.offer(n);
            }
        }
        else{
            while(!q1.isEmpty()){
                n=q1.poll();
                if(q1.isEmpty()){
                    return n;
                }
                q2.offer(n);
            }
        }
        return n;
    }

    public int top() {
        int n=0;
        if(q1.isEmpty()){
            while(!q2.isEmpty()){
                n=q2.poll();
                q1.offer(n);
                if(q2.isEmpty()){
                    return n;
                }
            }
        }
        else{
            while(!q1.isEmpty()){
                n=q1.poll();
                q2.offer(n);
                if(q1.isEmpty()){
                    return n;
                }
            }
        }
        return n;
    }

    public boolean empty() {
        if(q1.isEmpty()&&q2.isEmpty()){
            return true;
        }
        else{
            return false;
        }
    }
}
public class Test {
    public static void main(String[] args) {
        MyStack stack=new MyStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.empty());
    }
}
